package cn.suchan.jianzhi.q27_permutation;

import java.text.Collator;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * 知识点：字符串的排序
 * 题目描述
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 输入描述:
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 *
 * @author suchan
 * @date 2019/05/30
 */
public class Solution {

    /**
     * 效率不是很好
     *
     * @param str
     * @return
     */
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> permutationList = new ArrayList<>();
        if (str.isEmpty() || str == null) {
            return permutationList;
        }

        // 对每个字符串都进行一次字符顺序调换
        // 例如：str="abc";
        // 首先permutationList只存放有“abc”，
        // 经过一次顺序调换之后，permutationList里会存放有“abc”、“bac”、“cab”、“acb”、“cba”，
        // 然后再从“bac”开始继续进行顺序调换，以此类推。
        permutationList.add(str);
        for (int p = 0; p < permutationList.size(); p++) {
            char[] chars = permutationList.get(p).toCharArray();
            for (int i = 0; i < chars.length; i++) {
                for (int j = 0; j < chars.length; j++) {
                    if (i != j) {
                        char[] tempChars = chars;
                        char temp = tempChars[i];
                        tempChars[i] = tempChars[j];
                        tempChars[j] = temp;
                        String result = String.valueOf(tempChars);
                        // 如果调换顺序之后的字符串已存在则不再重复存入permutationList中
                        if (!permutationList.contains(result)) {
                            permutationList.add(result);
                        }
                    }
                }
            }
        }

        // 按字典顺序排序
        Collections.sort(permutationList, (p1, p2) -> {
            Comparator<Object> com = Collator.getInstance(java.util.Locale.CHINA);
            return com.compare(p1, p2);
        });

        return permutationList;
    }

    /**
     * 参照别人的做法
     * <p>
     * 1.列出所有字符串用递归求解。
     * 对于n个字符串的排列问题。如果能生成n - 1个元素的全部排列结果，就能生成n个元素的全部排列结果。
     * 以abc为例：
     * F(String str ,int start ,int end)
     * F(abc,start,end)=F(abc,start+1,end)+F(bac,start+1,end)+F(cba,start+1,end)
     * F(abc,start,end)=abc (start==end)
     * </p>
     * <p>
     * 2.结果按字典顺序输出，这就用到了强大的TreeSet了，直接排好序。
     * 又因为题目中要求返回ArrayList类型，故将TreeSet中元素全部加入ArrayList中.
     * </p>
     *
     * @param str
     * @return
     */
    public ArrayList<String> Permutation1(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] chars = str.toCharArray();
        // 用于排序输出(可以直接排好序)
        TreeSet<String> res = new TreeSet<>();
        getResult(chars, 0, str.length() - 1, res);
        result.addAll(res);
        return result;
    }

    public void getResult(char[] chars, int start, int end, TreeSet<String> res) {
        if (start == end) {
           // System.out.println(String.valueOf(chars));
            res.add(String.valueOf(chars));
        } else {
            for (int i = start; i <= end; i++) {
                //交换位置
                swap(chars, start, i);
                //递归  这个递归捋得我好累啊
                getResult(chars, start + 1, end, res);
                //System.out.println("start==>" + start + " & i==>" + i + " & end==>" + end);
                //再把位置换回来，保证下次换位是正确的
                swap(chars, start, i);
                //System.out.println("==============================");
                //System.out.println("start==>" + start + " & i==>" + i + " & end==>" + end);
            }
        }
    }

    /**
     * 交换位置
     *
     * @param chars
     * @param a
     * @param b
     */
    public void swap(char[] chars, int a, int b) {
        if (a != b) {
            char temp = chars[a];
            chars[a] = chars[b];
            chars[b] = temp;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //ArrayList<String> permutation = solution.Permutation("abc");
        //System.out.println("my==>" + permutation);
        ArrayList<String> permutation1 = solution.Permutation1("abcde");
        System.out.println("his==>" + permutation1);
    }
}
